What's the Static Searching Problem?

	given integer X and array A
	return position of X in A 
	or indicate X is not present
	array A is never altered



What's a Sequential Search?

	step through data sequentially until match
	needed when array not sorted


What's the Big-Oh bound on a Sequential Search?

	unsuccessful search needs N compares
	worst-case successful search needs N compares
	average-case successful search needs N/2 compares
	all O(N)



Suppose the array is sorted.
Can you do better than sequential search?

	Binary Search
	like searching in a phone book
	array must be sorted
	repeatedly divide array in half until match


How does this code work?

    public static int binarySearch( int [ ] a, int x )
    {
        int low = 0;
        int high = a.length - 1;
        int mid;

        while( low <= high )
        {
            mid = ( low + high ) / 2;

            if( x > a[ mid ] )
                low = mid + 1;
            else if( x < a[ mid ] )
                high = mid - 1;
            else
                return mid;
        }

        return NOT_FOUND;     // NOT_FOUND = -1
    }



Show the steps of a binary search for 6 in the array.

	1 2 4 5 6 8 9

	low = 0
	high = 6
	mid = 3

	low = 4
	high = 6
	mid = 5

	low = 4
	high = 4
	mid = 4



Show the steps of a binary search for 3 in the array.

	1 2 4 5 6 8 9

	low = 0
	high = 6
	mid = 3

	low = 0
	high = 2
	mid = 1

	low = 2
	high = 2
	mid = 2



What's the Big-Oh bound on a Binary Search?

	unsuccessful search needs floor(logN)+1 loops
	worst-case needs floor(logN) loops
	average-case needs floor(logN)-1 loops
	all O(logN)



DEMO	(compare running time of sequential and binary searches)